Collective communication in which the plurality of processors communicate with each other simultaneously is required to be possible to ensure that parallel processing is executed by a parallel computer having a plurality of processors connected through a network. Japanese Patent No. 2601591 describes a method when all processors of a parallel computer communicate with each other. FIG. 11 of this Japanese Patent shows a process flow of this method, in which an inter-processor synchronization is performed between all the processors during a phase of communication made with a specific communication destination (called a partial communication phase) to synchronize phases of all the processors. This is done for the purpose that communication destinations are simultaneously switched over all the processors through the phase synchronization. When it is not done, the phases of the processors shift, so that a collision between the communications occurs on a communication path, although the communications should not originally collide. For example, it is described in a phase management table in FIG. 9 of the Japanese Patent that there are a communication from PE2 to PE3 in a phase 2 and a communication from PE8 to PE3 in a phase 3. If PE8 enters the phase 3 and communicates with PE3 while PE2 is communicating with PE3 in the phase 2, the two communications with PE3 occur, thus halving performance. In this Japanese Patent, in order to avoid collision on a communication path, a phase management table is provided to perform the inter-processor synchronization over all the processors between phases. Thus, a method is proposed of synchronizing the phases between all the processors to allow high-speed communication between all the processors.
One of problems involved in the above related technique is in that a time for the inter-processor synchronization becomes an overhead of a time for an original communication, to degrade performance of the collective communication, since the inter-processor synchronization needs to be performed between one partial communication phase and another partial communication phase by all the processors participating in the collective communication. This is because some communications are required for the inter-processor synchronization between a plurality of processors, thus requiring some time period. Even if the plurality of processors execute inter-processor synchronization commands simultaneously, some time period is required for completion of the synchronization. This time required for the completion of inter-processor synchronization usually increases as the number of processors increases. This is because a large number of processors results in long physical distances between the processors. Therefore, as a size of the parallel computer increases, the time period required for the inter-processor synchronization increases, so that the overhead of the inter-processor synchronization between one partial communication phase and another partial communication phase increases in the related technique, resulting in performance degradation in the collective communication.